1151. Кладоискатель

Юный кладоискатель Рома прошел курс обучения по специальности “кладовое дело”, и теперь проходит летнюю практику. Летняя практика проходит близ поселка “Каменные Зори” и длится ровно b дней. Каждый день Рома находит a закопанных в окрестности монет. Таким образом, в конце первого дня у него было a монет, в конце второго 2 * a, а по окончании практики у Ромы должно накопиться b * a монет.

Если в конце дня ответственный преподаватель замечал, что число Роминых монет делится на b, то Роме разрешалось взять с полки пирожок, который он тут же съедал. Помогите Роме посчитать, сколько пирожков он съест за время прохождения практики.

Вход. Два целых числа a и b (1 ≤ a, b ≤ 10⁹).

Выход. Выведите число съеденных Ромой пирожков.

Пример входа	Пример выхода
2 1	1

РЕШЕНИЕ

НОД

Анализ алгоритма

Количество съеденных Ромой пирожков равно НОД (a, b).

Реализация алгоритма

Фукция gcd вычисляет наибольший общий делитель чисел a и b.

int gcd(int a, int b)

{

return (!b) ? a : gcd(b, a % b);

}

Читаем входные данные. Вычисляем и выводим ответ.

scanf("%d %d", &a, &b);

d = gcd(a, b);

printf("%d\n", d);